// 给定链表头节点head，返回链表的中间节点，如果有两个中间节点，则返回第二个中间节点

// 1. 单指针解法
// 先遍历一遍链表，统计节点个数n，再遍历到n/2的位置，返回中间节点

// 空间复杂度O(n)
// 时间复杂度O(1)
const { ListNode, LinkedList } = require('../../1. 链表基础/1. 建立线性链表')
function middeNode1(head) {
    let n = 0
    let cur = head
    while (cur) {
        n += 1
        cur = cur.next
    }
    let k = 0
    cur = head
    while (k < Math.floor(n / 2)) {
        k += 1
        cur = cur.next
    }
    return cur
}
 
// let list = new LinkedList([2, 5, 1, 7, 3, 9])
let list = new LinkedList([2, 5, 1, 7])
console.log(middeNode1(list.head))


//2. 快慢指针解法
//  1. 使用slow和fast指针指向链表头节点
//  2. slow移动一步，fast每次移动二步
//  3. fast移动到链表尾部时跳出循环体，此时slow指向链表中间位置
//  4. 返回slow指针

// 空间复杂度O(n)
// 时间复杂度O(1)

function middleNode(head) {
    let fast = head
    let slow = head
    while (fast && fast.next) {
        slow = slow.next
        fast = fast.next.next
    }
    return slow
}
// let list2 = new LinkedList([2, 5, 1, 7, 3, 9])
let list2 = new LinkedList([2, 5, 1, 7])
console.log(middleNode(list2.head))